package JavaCode.random_records.N301_400;

import java.util.*;

/**
 * author:fangjie
 * time:2019/10/15
 */
public class N310_minimum_height_trees {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer>[] graphs=new List[n];
        for (int i=0;i<n;i++)graphs[i]=new ArrayList<>();
        for (int[] edge:edges)
        {
            graphs[edge[0]].add(edge[1]);
            graphs[edge[1]].add(edge[0]);
        }

        int min=Integer.MAX_VALUE;
        Map<Integer,Map<Integer,Integer>> map=new HashMap<>();
        List<Integer> res=new ArrayList<>();
        for (int i=0;i<n;i++)
        {
            int t=slove(-1, i,map, graphs);
            if(t==min)res.add(i);
            else if(t<min)
            {
                min=t;
                res.clear();
                res.add(i);
            }
        }
        return res;

    }

    private int slove(int pre, int cur, Map<Integer,Map<Integer,Integer>> map, List<Integer>[] graphs) {
        if (map.containsKey(pre))
        {
            int v=map.get(pre).getOrDefault(cur, -1);
            if(v!=-1)return v;
        }
        int res=0;
        for (int next:graphs[cur])
        {
            if(pre==next)continue;
            int len=slove(cur, next, map, graphs)+1;
            res=Math.max(res,len);
        }
        map.putIfAbsent(pre,new HashMap<>());
        map.get(pre).put(cur,res);
        return res;
    }
}
/**
 * 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
 *
 * 格式
 *
 * 该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
 *
 * 你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
 *
 * 示例 1:
 *
 * 输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
 *
 *         0
 *         |
 *         1
 *        / \
 *       2   3
 *
 * 输出: [1]
 * 示例 2:
 *
 * 输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
 *
 *      0  1  2
 *       \ | /
 *         3
 *         |
 *         4
 *         |
 *         5
 *
 * 输出: [3, 4]
 * 说明:
 *
 *  根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
 * 树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-height-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
